#include "stack_queue.h"
#include "cctype"
using namespace std;

listNode::listNode():next(NULL),data(0) {}

listNode::listNode(int nodeData,listNode* succ){
    data=nodeData;
    next=succ;
}
//创建栈
MyStack::MyStack(){
    topNode=NULL;
    stackSize=0;
}

//清除栈内元素,销毁栈
MyStack::~MyStack(){
    listNode* curr=topNode;
    while(curr!=NULL){
        listNode* temp=curr;
        curr=curr->next;
        delete temp;
    }
    topNode=NULL;
    stackSize=0;
}

//入栈
bool MyStack::push(const int& value){
    listNode* newNode=new listNode(value,topNode);
    if(newNode==NULL){
        return false;
    }
    topNode=newNode;
    stackSize++;
    return true;
}

//出栈
bool MyStack::pop(int& item){
    if(topNode==NULL){
        return false;
    }
    listNode* newNode=topNode;
    item=topNode->data;
    topNode=topNode->next;
    delete newNode;
    stackSize--;
    return true;
}

//返回栈顶元素
bool MyStack::getTop(int& item){
    if(topNode==NULL){
        return false;
    }
    item=topNode->data;
    return true;
}

void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}

//队列初始化
MyQueue::MyQueue(const int& capacity){
    this->capacity=capacity+1; 
    queue=new int[this->capacity];
    front=0;
    rear=0;
    
}

//销毁队列
MyQueue::~MyQueue(){
    delete[] queue;
}

bool MyQueue::isFull(){
    if((rear+1)%capacity==front){
        return true;
    }
    return false;
}

//入队
bool MyQueue::enQueue(const int& value){
    if(isFull()){
        return false;
    }
    queue[rear]=value;
    rear=(rear+1)%capacity;
}

//出队
bool MyQueue::deQueue(int& item){
    if(front==rear){
        return false;
    }
    item=queue[front];
    front=(front+1)%capacity;
    return true;
}

//返回队头元素
bool MyQueue::getFront(int& item){
    if(front==rear){
        return false;
    }
    item=queue[front];
    return true;
}

void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

bool isoperator(char c){
    if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'){
        return true;
    }
    else{return false;}
}

int getpriority(char op){
    switch(op){
        case '+':
        case '-': return 1;
        case '*': 
        case '/': return 2;
        case '(': return 0;
        default: return -1;
    }
}

bool postfixExpression(const string& infix,string& result){
    MyStack opStack;
    result="";
    for(int i=0;i<infix.length();i++){
        char c=infix[i];
        if(isdigit(c)){
            result+=c;
            //result+=' ';
        }
        else if(c=='('){
            opStack.push(c);
        }
        else if(c==')'){
            int topop;
            while(opStack.getTop(topop)&&(char)topop!='('){
                opStack.pop(topop);
                result+=(char)topop;
                //result+=' ';
            }
            if(!opStack.getTop(topop)||(char)topop!='('){
                result="Expression is wrong!";
                return false;
            }
            opStack.pop(topop);
        }
        else if(isoperator(c)){
            int topop;
            while(opStack.getTop(topop)&&getpriority((char)topop)>=getpriority(c)){
                opStack.pop(topop);
                result+=(char)topop;
                //result+=' ';
            }
            opStack.push(c);
        }
        else{
            result="Expression is wrong!";
            return false;
        }
    }
    int remainingop;
    while(opStack.pop(remainingop)){
        if((char)remainingop=='('){
            result="Expression is wrong!";
            return false;
        }
        result+=remainingop;
        //result+=' ';
    }
    if(!result.empty()&&result.back()==' '){
        result.pop_back();
    }
    return true;
}

int calculate(int a,int b,char op){
    switch(op){
        case '+':return a+b;
        case '-':return a-b;
        case '*':return a*b;
        case '/':
        if(b==0){
            throw runtime_error("Division by zero");
        }
        return a/b;
        default:return 0;
    }
}

bool expressionVal(const string& expression, int& result){
    string postfix;
    if(!postfixExpression(expression,postfix)){
        result=0;
        return false;
    }
    MyStack numstack;
    for(size_t i=0;i<postfix.length();i++){
        char c=postfix[i];
        if(c==' '){
            continue;
        }
        else if(isdigit(c)){
            numstack.push(c-'0');
        }
        else if(isoperator(c)&&c!='('&&c!=')'){
            int a,b;
            if(!numstack.pop(b)||!numstack.pop(a)){
                result=0;
                return false;
            }
            try{
                int calcresult=calculate(a,b,c);
                numstack.push(calcresult);
            }
            catch(const runtime_error&){
                result=0;
                return false;
            }
        }
        else{
            result=0;
            return false;
        }
    }
    if(!numstack.pop(result)){
        result=0;
        return false;
    }
    int temp;
    if(numstack.getTop(temp)){
        result=0;
        return false;
    }
    return true;
}

void yanghui(const int& n){
    if(n<=0){
        return;
    }
    MyQueue queue(n+2);

    queue.enQueue(1);
    //queue.printQueue();

    for(int i=1;i<=n;i++){
        queue.enQueue(1);
        int pre=0;
        int cur;
        int row=i;
        for(int j=0;j<row;j++){
            queue.deQueue(cur);
            if(j>0){
                queue.enQueue(pre+cur);
            }
            pre=cur;
        }
        queue.enQueue(1);
        if(i>=1){
            queue.printQueue();
        }
    }

}